\section{Previous work}

\subsection{Gelernter et al}

The idea of first-class environments is of course not new.
Gelernter et al \cite{Gelernter:1987:EFC:41625.41634} defined a
language called ``Symmetric Lisp'' in which the programmer is allowed
to evaluate expressions with respect to a particular first-class
environment.  They suggest using this kind of environment as a
replacement for a variety of constructs, including closures,
structures, classes, and modules.  The present paper does not have
this kind of ambitious objective, simply because we do not know how to
obtain excellent performance for all these constructs with our
suggested protocol.

\subsection{Miller and Rozas}

Miller and Rozas \cite{Miller:1991:FVF:113825.113826} describe a set
of extensions for the \scheme{} programming language.  In their paper,
Miller and Rozas also claim that their proposed first-class
environments could serve as a basis for an object-oriented system.
Like the present work, Miller and Rozas are concerned with
performance, and a large part of their paper is dedicated to this
aspect of their proposal.

In their paper, they show that the extensions incurs no performance
penalty for code that does not use it.  However, for code that uses
the extension, the compiler defers accesses to the first-class
environment to the \emph{interpreter}, thereby imposing a performance
penalty in code using the extension.

The basic mechanism of their proposed extension is a \emph{special
  form} named \texttt{make-environment} that creates and returns an
environment in which the code in the \emph{body} of that special form
is executed.  The operators \texttt{lexical-reference} and
\texttt{lexical-assignment} are provided to access bindings in a
first-class environment.

From the examples in the paper, it is clear that their first-class
environments are meant to be used at a much finer level of granularity
than ours.

\subsection{Queinnec and Roure}

Queinnec and de Roure \cite{Queinnec:1996:SCT:232627.232653} proposed
a protocol for first-class environments in the context of the
\scheme{} programming language.  Their motivation is different from
ours, in that their environments are meant to be part of the
user-visible interface so as to simplify sharing of various objects.
However, like the present work, they are also concerned with
performance, and they show how to implement their protocol without
serious performance degradation.

The environments proposed by Queinnec and de Roure were clearly meant
to allow for \emph{modules} as collections of \emph{bindings} where
the bindings can be shared by other modules through the use of the new
operators \texttt{export} and \texttt{import}.  In contrast, the
first-class environments proposed in the present paper are not meant
to allow such sharing of bindings, though our proposal might allow
such sharing for function and variable bindings.

The paper by Queinnec and de Roure contains a thorough survey of other
work related to first-class environments that will not be repeated
here.

\subsection{Garret's lexicons}

Ron Garret describes \emph{lexicons}%
\footnote{Unpublished document.  A PDF version can be found here:
  http://www.flownet.com/ron/lisp/lexicons.pdf.}
which are said to be first-class global environments.  However, the
concept of a lexicon is very different from the concept of a
first-class global environment as defined in this paper.

For one thing, a lexicon is ``a mapping from symbols to bindings'',
which excludes a per-environment set of packages, simply because
package names are not symbols, but strings.

Furthermore, a clearly stated goal of lexicons is to create a
different \lisp{} dialect targeted to new users or to users that have
prior experience with languages that are different from \lisp{}.

One explicit goal of lexicons is to replace \commonlisp{} packages, so
that there is a single system-wide symbol with a particular name.  In
contrast, the first-class environments presented in this paper do not
in any way affect the package system.  It should be noted that with
our first-class environments, \emph{symbols are still unique}, i.e.,
for a given package $P$ and a given symbol name $N$, there is at most
one symbol with the name $N$ in $P$; independently of the number of
first-class environments in the system.

Garret discusses the use of lexicons as modules and shows examples
where functions defined in one lexicon can be imported into a
different lexicon.  The use of the operator \texttt{use-lexicon}
imports all the \emph{bindings} of an explicitly-mentioned lexicon
into the current one.  In the present work, we do not emphasize the
possibility of sharing bindings between first-class environments.
However, since functions and global values of special variables are
stored in indirections called \emph{cells} in our environment, such
sharing of bindings would also be possible in the first-class
environments presented in this paper.
